package com.xyzboom.compiler.fa

import com.fasterxml.jackson.annotation.JsonCreator
import com.fasterxml.jackson.annotation.JsonProperty
import com.fasterxml.jackson.core.JsonParser
import com.fasterxml.jackson.databind.*
import com.fasterxml.jackson.databind.annotation.JsonDeserialize
import com.fasterxml.jackson.databind.annotation.JsonSerialize
import com.fasterxml.jackson.databind.deser.ContextualDeserializer
import com.fasterxml.jackson.databind.deser.std.StdDeserializer
import com.fasterxml.jackson.databind.ser.std.StdDelegatingSerializer
import com.fasterxml.jackson.databind.type.TypeBindings
import com.fasterxml.jackson.databind.type.TypeFactory
import com.fasterxml.jackson.databind.util.Converter
import com.fasterxml.jackson.databind.util.StdConverter
import com.xyzboom.compiler.NoArg
import com.xyzboom.compiler.excepitons.fa.IllegalEdgeTypeException
import com.xyzboom.compiler.fa.EdgeType.*
import mu.KotlinLogging
import kotlin.reflect.full.declaredMemberProperties
import kotlin.reflect.jvm.javaField

private val logger = KotlinLogging.logger { }

@JsonSerialize(converter = DFA.Companion.DFASerializerConverter::class)
@JsonDeserialize(using = DFA.Companion.DFADeserializer::class)
//@JsonSerialize(using = DFA.Companion.DFASerializer::class)
class DFA<T, K>(
    val nodeIn: DFANode<T, K>,
    val endNodes: MutableSet<DFANode<T, K>>,
    val allNodes: MutableSet<DFANode<T, K>>,
) {
    companion object {
        @JvmStatic
        @JsonCreator(mode = JsonCreator.Mode.PROPERTIES)
        fun createDFA(
            @JsonProperty("i") i: Int,
            @JsonProperty("e") e: HashSet<Int>,
            @JsonProperty("m") m: HashMap<Int, HashMap<FAEdge<Char>, Int>>,
        ): DFA<Int, Char> {
            return fromStateMap(i, e, m)
        }

        @NoArg
        class DFADelegator<T, K>(
            val i: T,
            val e: HashSet<T>,
            val m: HashMap<T, HashMap<FAEdge<K>, T>>,
        ) {
            init {
                for (p in this::class.declaredMemberProperties) {
                    val jf = p.javaField!!
                    logger.trace { jf.genericType }
                    logger.trace { jf.genericType::class }
                }
            }
        }

        class DFASerializerConverter<T, K> : StdConverter<DFA<T, K>, DFADelegator<T, K>>() {
            override fun convert(value: DFA<T, K>): DFADelegator<T, K> {
                return DFADelegator(
                    value.nodeIn.value,
                    HashSet(value.endNodes.map { it.value }),
                    value.stateMap
                )
            }
        }

        class DFASerializer<T, K>
            : StdDelegatingSerializer {
            constructor() : super(DFASerializerConverter<T, K>())

            private constructor(
                converter: Converter<Any, *>?,
                delegateType: JavaType?,
                delegateSerializer: JsonSerializer<*>?,
            ) : super(converter, delegateType, delegateSerializer)

            override fun withDelegate(
                converter: Converter<Any, *>?,
                delegateType: JavaType?,
                delegateSerializer: JsonSerializer<*>?,
            ): StdDelegatingSerializer {
                return DFASerializer<Any, Any>(converter, delegateType, delegateSerializer)
            }
        }

        class DFADeserializerConverter<T, K> : Converter<DFADelegator<T, K>, DFA<T, K>> {
            val t: T? = null
            val k: K? = null

            init {
                for (tp in this::class.java.typeParameters) {
                    logger.trace { tp }
                }
            }

            override fun convert(value: DFADelegator<T, K>): DFA<T, K> {
                return fromStateMap(value.i, value.e, value.m)
            }

            override fun getInputType(typeFactory: TypeFactory): JavaType {
                return findConverterType(typeFactory).containedType(0)
            }

            override fun getOutputType(typeFactory: TypeFactory): JavaType {
                return findConverterType(typeFactory).containedType(1)
            }

            private fun findConverterType(tf: TypeFactory): JavaType {
                val thisType = tf.constructType(javaClass)
                val convType = thisType.findSuperType(Converter::class.java)
                check(!(convType == null || convType.containedTypeCount() < 2)) { "Cannot find OUT type parameter for Converter of type " + javaClass.name }
                return convType
            }
        }

        class DFADeserializer
            : StdDeserializer<DFA<Any?, Any?>>, ContextualDeserializer {
            @Suppress("Unused")
            constructor() : super(DFA::class.java)
            constructor(targetType: JavaType) : super(targetType)

            override fun deserialize(p: JsonParser?, ctxt: DeserializationContext): DFA<Any?, Any?> {
                val targetType = valueType
                val targetParameterizedTypes: TypeBindings = targetType.bindings

                val parameterizedDFADelegatorType: JavaType = ctxt.typeFactory.constructParametricType(
                    DFADelegator::class.java,
                    targetParameterizedTypes
                )
                val dfaDelegator = ctxt.readValue<DFADelegator<Any?, Any?>>(p, parameterizedDFADelegatorType)
                return fromStateMap(dfaDelegator.i, dfaDelegator.e, dfaDelegator.m)
            }

            override fun createContextual(ctxt: DeserializationContext, property: BeanProperty?): JsonDeserializer<*> {
                val targetType = ctxt.contextualType
                return DFADeserializer(targetType)
            }

        }

        fun <T, K> fromStateMap(
            nodeIn: T, endNodes: Set<T>, stateMap: HashMap<T, HashMap<FAEdge<K>, T>>,
        ): DFA<T, K> {
            val rNodeIn = DFANode<T, K>(nodeIn)
            val rAllNodes = HashSet<DFANode<T, K>>()
            val rEndNodes = HashSet<DFANode<T, K>>()
            rAllNodes.add(rNodeIn)
            val nodeMap = HashMap<T, DFANode<T, K>>()
            nodeMap[nodeIn] = rNodeIn
            val visited = HashSet<T>()
            val stack = ArrayDeque<T>()
            stack.addLast(nodeIn)
            if (endNodes.contains(nodeIn)) {
                rEndNodes.add(rNodeIn)
            }
            while (stack.isNotEmpty()) {
                val nodeNow = stack.removeFirst()
                if (visited.contains(nodeNow)) continue
                val rNodeNow = nodeMap.getOrPut(nodeNow) {
                    val result = DFANode<T, K>(nodeNow)
                    if (endNodes.contains(nodeNow)) {
                        rEndNodes.add(result)
                    }
                    rAllNodes.add(result)
                    result
                }
                val stateTo = stateMap[nodeNow] ?: continue
                for (stateEntry in stateTo) {
                    val state = stateEntry.value
                    val edge = stateEntry.key
                    rNodeNow.next[edge] = nodeMap.getOrPut(state) {
                        val result = DFANode<T, K>(state)
                        if (endNodes.contains(state)) {
                            rEndNodes.add(result)
                        }
                        rAllNodes.add(result)
                        result
                    }
                    stack.add(state)
                }
                visited.add(nodeNow)
            }
            return DFA(rNodeIn, rEndNodes, rAllNodes)
        }
    }

    fun acceptable(s: List<K>): Boolean {
        return if (s.isNotEmpty()) {
            acceptFrom(0, s, nodeIn) == s.size + 1
        } else {
            endNodes.contains(nodeIn)
        }
    }

    private fun acceptFrom(
        index: Int, s: List<K>, state: DFANode<T, K>?, greedy: Boolean = true,
    ): Int {
        state ?: return index
        if (!greedy && endNodes.contains(state)) {
            return index
        }
        if (index == s.size) {
            return if (endNodes.contains(state)) {
                s.size + 1
            } else {
                -1
            }
        }
        val reverseThis = state.next.any { it.key.value == s[index] }
        val nextStates = state.next.filter {
            val result = when (it.key.type) {
                DOT_ANY -> s[index] != '\r'
                        && s[index] != '\n'

                REVERSE -> it.key.value != s[index] && !reverseThis
                NORMAL -> it.key.value == s[index]
                MOVE_IN, REDUCE, GOTO ->
                    throw IllegalEdgeTypeException("Illegal edge type ${it.key.type} in fa.This type only used in grammar")
            }
            result
        }
        if (nextStates.isEmpty()) {
            return if (endNodes.contains(state))
                index
            else
                -1
        }
        return if (greedy) nextStates.maxOf {
            return@maxOf acceptFrom(index + 1, s, it.value)
        } else {
            val nextIndex = nextStates.map {
                return@map acceptFrom(index + 1, s, it.value, false)
            }.filter { it != -1 }
            if (nextIndex.isEmpty()) {
                -1
            } else nextIndex.min()
        }
    }

    /**
     * 从指定串的指定位置开始尝试贪婪匹配，直到匹配失败
     * @return 最后一个匹配成功的位置后面
     */
    fun acceptFrom(index: Int, s: List<K>, greedy: Boolean = true): Int =
        acceptFrom(index, s, nodeIn, greedy)

    fun intStateDFA(): DFA<Int, K> {
        var now = 0
        val newEnd = HashSet<DFANode<Int, K>>()
        val newAll = HashSet<DFANode<Int, K>>()
        val oldToNew = HashMap<DFANode<T, K>, DFANode<Int, K>>()
        val startNode = DFANode<Int, K>(0)
        oldToNew[nodeIn] = startNode
        newAll.add(startNode)
        if (endNodes.contains(nodeIn)) {
            newEnd.add(startNode)
        }
        for (s in allNodes) {
            if (s == nodeIn) {
                continue
            }
            now++
            val nowNode = DFANode<Int, K>(now)
            if (endNodes.contains(s)) {
                newEnd.add(nowNode)
            }
            newAll.add(nowNode)
            oldToNew[s] = nowNode
        }
        for (oldNode in allNodes) {
            val newNode = oldToNew[oldNode]!!
            oldNode.next.forEach {
                newNode.next[it.key] = oldToNew[it.value]!!
            }
        }
        return DFA(startNode, newEnd, newAll)
    }

    val stateMap: HashMap<T, HashMap<FAEdge<K>, T>>
        get() {
            val dfaStateMap = HashMap<T, HashMap<FAEdge<K>, T>>()
            val visited = HashSet<T>()
            for (nodeNow in allNodes) {
                if (visited.contains(nodeNow.value)) {
                    continue
                }
                for (entryNext in nodeNow.next) {
                    val nextNode = entryNext.value
                    dfaStateMap.getOrPut(nodeNow.value) { HashMap() }
                        .getOrPut(entryNext.key) { nextNode.value }
                }
                visited.add(nodeNow.value)
            }
            return dfaStateMap
        }

    fun getSimplest(): DFA<MutableSet<T>, K> {//Use Myhill-Nerode
        val dfaStateMap = stateMap
        //<editor-fold desc="创建DFA中所有状态的对">
        val sign = HashMap<T, HashMap<T, Boolean>>()
        val allStates = allNodes.map { it.value }
        val endStates = endNodes.map { it.value }
        val nonEndStates = allStates.subtract(endStates.toSet())
        for ((stateCount, state0) in allStates.withIndex()) {
            for ((nowCount, state1) in allStates.withIndex()) {
                if (nowCount >= stateCount) break
                sign.getOrPut(state0) { HashMap() }[state1] = false
            }
        }
        //</editor-fold>
        //<editor-fold desc="标记所有(Qa, Qb), s.t.  Qa是终态，Qb是非终态">
        preSign(allStates, nonEndStates, sign)
        //</editor-fold>
        doSign(sign, dfaStateMap)
        val (startResult, allResult) = unionResult(allStates, sign)
        val triple = finalResult(allResult, startResult, endStates, dfaStateMap)
        val nodeInResult = triple.first
        val endNodesResult = triple.second
        val allNodesResult = triple.third
        return DFA(nodeInResult, endNodesResult, allNodesResult)
    }

    private inline fun finalResult(
        allResult: HashSet<MutableSet<T>>,
        startResult: HashSet<T>,
        endStates: List<T>,
        dfaStateMap: HashMap<T, HashMap<FAEdge<K>, T>>,
    ): Triple<DFANode<MutableSet<T>, K>, HashSet<DFANode<MutableSet<T>, K>>, HashSet<DFANode<MutableSet<T>, K>>> {
        var nodeInResult = DFANode<MutableSet<T>, K>(HashSet())
        val endNodesResult = HashSet<DFANode<MutableSet<T>, K>>()
        val allNodesResult = HashSet<DFANode<MutableSet<T>, K>>()
        val oldToNew = HashMap<MutableSet<T>, DFANode<MutableSet<T>, K>>()
        for (result in allResult) {
            val newResult = DFANode<MutableSet<T>, K>(result)
            allNodesResult.add(newResult)
            oldToNew[result] = newResult
            if (result == startResult) {
                nodeInResult = newResult
            }
            if (result.any { endStates.contains(it) }) {
                endNodesResult.add(newResult)
            }
        }
        //遍历所有预先生成的结果
        for (result in allResult) {
            val newState = oldToNew[result]!!//从map中查找需要的新结果
            for (node in result) {//再次遍历
                val nextNodes = dfaStateMap[node] ?: continue
                for (nextEntry in nextNodes) {//遍历结果的邻接点
                    for (oEntry in oldToNew) {
                        if (oEntry.key.contains(nextEntry.value)) {//发现有对应的边
                            newState.next[nextEntry.key] = oEntry.value
                        }
                    }
                }
            }
        }
        return Triple(nodeInResult, endNodesResult, allNodesResult)
    }

    private inline fun unionResult(
        allStates: List<T>,
        sign: HashMap<T, HashMap<T, Boolean>>,
    ): Pair<HashSet<T>, HashSet<MutableSet<T>>> {
        val startResult = HashSet<T>()
        startResult.add(nodeIn.value)
        val endResult = HashSet<MutableSet<T>>()
        val allResult = HashSet<MutableSet<T>>()
        allResult.add(startResult)
        if (endNodes.contains(nodeIn)) {
            endResult.add(startResult)
        }
        allResult.add(startResult)
        val visited = HashSet(startResult)
        while (visited.size < allNodes.size) {
            for (state in allStates.subtract(visited)) {
                visited.add(state)
                if (!(sign[state] ?: continue).containsValue(false)) {
                    continue
                }
                //从标记中筛选出没有打标签的状态进行合并
                for (entry in sign[state]?.filter { !it.value && (it.key != state) } ?: continue) {
                    val needToUnion = entry.key
                    var unionResult = false
                    for (stateResult in allResult) {
                        if (!stateResult.contains(state) && !stateResult.contains(needToUnion)) {
                            continue
                        }
                        unionResult = true
                        stateResult.apply {
                            add(needToUnion)
                            add(state)
                        }
                        break
                    }
                    if (!unionResult) {
                        val newUnion = HashSet<T>().apply {
                            add(state)
                            add(needToUnion)
                        }
                        allResult.add(newUnion)
                    }
                }
            }
        }
        for (state in allStates) {
            //集合中的元素没有符合lambda条件的
            if (allResult.none { it.contains(state) }) {
                val needToAdd = HashSet<T>()
                needToAdd.add(state)
                allResult.add(needToAdd)
            }
        }
        return Pair(startResult, allResult)
    }

    private inline fun doSign(
        sign: HashMap<T, HashMap<T, Boolean>>,
        dfaStateMap: HashMap<T, HashMap<FAEdge<K>, T>>,
    ) {
        val guessAlphabet = HashSet<FAEdge<K>>()
        allNodes.forEach { guessAlphabet.addAll(it.next.keys) }
        while (true) {
            var newSignAdded = false
            for (entryA in sign) {
                val stateA = entryA.key
                for (entryB in entryA.value) {
                    val stateB = entryB.key
                    if (sign[stateA]?.get(stateB) == true) {
                        continue
                    }
                    var canSign = false
                    for (x in guessAlphabet) {
                        val moveA = dfaStateMap[stateA]?.get(x)
                        val moveB = dfaStateMap[stateB]?.get(x)
                        if (sign[moveA]?.get(moveB) == true//有标记则为可区分的两个状态
                            || (moveA == null && moveB != null)//二者有一者对输入x不可接受，另一者接受，则可区分
                            || (moveB == null && moveA != null)
                        ) {
                            canSign = true
                            break
                        }
                    }
                    if (canSign) {
                        sign[stateA]?.set(stateB, true)
                        newSignAdded = true
                    }
                }
            }
            if (!newSignAdded) {
                break
            }
        }
    }

    private inline fun preSign(
        allStates: List<T>,
        nonEndStates: Set<T>,
        sign: HashMap<T, HashMap<T, Boolean>>,
    ) {
        for (endState in allStates) {
            for (nonEndState in nonEndStates) {
                if (sign[endState]?.get(nonEndState) != null) {
                    sign[endState]?.set(nonEndState, true)
                }
                if (sign[nonEndState]?.get(endState) != null) {
                    sign[nonEndState]?.set(endState, true)
                }
            }
        }
    }
}